﻿using System;

namespace ProblemsSet
{
    public class Problem_123 : BaseProblem
    {
        public override object GetResult()
        {
            const long max = 10000000000;

            long cnt = (long)Math.Sqrt(max/2);
            
            if (cnt%2 == 0)
                cnt++;

            var tmp = MathLogic.GetPrimeList(cnt);
            for (var i = tmp.Count-1; i >=0; i-=2)
            {
                var n = i + 1;
                if (2*n*tmp[i] < max)
                    return n+2;
            }
            return -1;
        }

        public override string Problem
        {
            get
            {
                return @"Let pn be the nth prime: 2, 3, 5, 7, 11, ..., and let r be the remainder when (pn1)n + (pn+1)n is divided by pn2.

For example, when n = 3, p3 = 5, and 43 + 63 = 280  5 mod 25.

The least value of n for which the remainder first exceeds 109 is 7037.

Find the least value of n for which the remainder first exceeds 1010.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 21035;
            }
        }

    }
}
